class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }
    int rob1(vector<int>& nums, int i, int j)
    {
        if (i > j) return 0;
        vector<int> f(nums.size());
        vector<int> g(nums.size());

        for (int k = i; k <= j; k++)
        {
            f[k] = g[k - 1] + nums[k];
            g[k] = max(f[k - 1], g[k - 1]);
        }
        return max(f[j], g[j]);
    }
};


class Solution {
public:
    int findMin(vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 1) return nums[0];
        int left = 0;
        int right = n - 1;
        while (left < right)
        {
            if (nums[right] > nums[left])
            {
                return nums[left];
            }
            else 
            {
                if (right - 1 >= left && nums[right - 1] > nums[right])
                {
                    return nums[right];
                }
                else if (left == right)
                {
                    return min(nums[left], nums[left + 1]);
                }
                left++;
                right--;
            }

        }    
        return min(nums[left - 1], nums[right]);
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int n = numbers.size();
        for (int i = 0; i < n; i++)
        {
            int num = numbers[i];
            int key = target - num;
            //
            int left = i + 1;
            int right = n - 1;
            while (left < right)
            {
                int mid = left + ((right - left + 1) >> 1);
                if (numbers[mid] > key) right = mid - 1;
                else left = mid;
            }
            if (numbers[left] == key) return {i + 1, left + 1};
        }    
        return {-1, -1};
    }
};